package Atop100.hash;

import java.util.HashMap;


//由于O(n)时间复杂度的限制，我们就不能采取先排序后遍历的思路。
//
//        针对O(n)时间复杂度的实现思路：遍历nums[]数组，利用Map存储元素nums[i]的值以及其所在连续序列的长度，此时基本只有两种情况：
//
//        数组中出现过元素nums[i]-1或nums[i]+1，意味着当前元素可以归入左或右序列，那么此时假如左右序列的长度分别为left、right，那么显然加入nums[i]后，这整段序列的长度为 1+left+right，而由于这一整段序列中，只可能在左右两端扩展，所以只需要更新左右两端的value值即可。
//        数组中未出现过元素nums[i]-1或nums[i]+1，意味着当前元素所在的连续序列就是自身（只有自己一个元素）。
//        但是！！总是有坑在等着我们跳：nums数组存在重复数字。
//
//        假设nums[] 数组为[2,4,3,3]，按照上面的逻辑，map（key->value）中2->1，4->1，当遇到3时，因为左右两端都存在，因此会直接更新2->2，4->2，再次遇到3，2->3，4->3，于是我们需要判断是否已经处理过3这个重复数字，方法就是每次处理的数字nums[i]，也在map中更新它的值，并且在遍历的时候先判断nums[i].value是不是0，如果不是0，那么意味着前面我们处理过了，直接跳过就好
//        ————————————————
//        版权声明：本文为CSDN博主「alan_gaohaodong」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
//        原文链接：https://blog.csdn.net/alan_gaohaodong/article/details/95314340
public class Class128 {
    public int longestConsecutive(int[] nums) {
        int max = 0;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i: nums){
            // 不是0  意味着之前处理过 就不用处理啦
            if(map.getOrDefault(i,0)==0){
                int left = map.getOrDefault(i-1,0);
                int right = map.getOrDefault(i+1,0);
                map.put(i,1+left+right);
                if(left!=0){
                    map.put(i-left,left+right+1);
                }
                if(right != 0){
                    map.put(i+right,left+right+1);
                }
                max = max>left+right+1?max:left+right+1;
            }
        }
        return max;
    }

    public int longestConsecutive1(int[] nums) {
int max=Integer.MIN_VALUE;

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int a:nums) {
            if (!map.containsKey(a)){
                int left = map.getOrDefault(a - 1, 0);
                int right = map.getOrDefault(a + 1, 0);
                map.put(a,1+left+right);
                if (left!=0){
                    map.put(a-left,1+left+right);
                }
                if (right!=0){
                    map.put(a+right,1+left+right);
                }
                max=Math.max(max,1+left+right);
            }



        }
        return  max;

    }


    public static void main(String[] args) {
        Class128 class128 = new Class128();
        int[] cur={0,3,7,2,5,8,4,6,0,1};
        System.out.println(class128.longestConsecutive(cur));
    }


}
